1. Field of the Invention
This invention relates generally to computer memory error correction systems and specifically to a signature detection system for locating clandestine or sinister code patterns during normal memory "scrubbing" operations.
2. Discussion of the Related Art
Semiconductor memory devices used to implement main memory elements of modern computer systems are manufactured with cell sizes and densities such that individual storage cells are susceptible to alpha particle failure. This is particularly true for dynamic RAMs (DRAMs). Materials used in packaging such memory devices inevitably include radioactive traces that decay to create alpha particles that penetrate the silicon die. An alpha particle hit can cause a bit storage cell to switch states, creating a "soft" bit error, as is well-known in the art. To eliminate the effects of such soft errors, error checking and correcting circuitry is used in modern computer memory systems. An error correction circuit operates to add an Error Correction Code (ECC) to each incoming data item as it is stored. Because the ECC is calculated as a known function of the bit sequence making up the data item being stored, it can be recalculated and checked against the earlier stored ECC when the same data item is later read. With simple ECCs, a single soft bit error can be corrected transparently to the user (before submitting the data item to the CPU), permitting tolerance of the usual transient alpha particle hits in DRAM systems.
Even though soft errors can be tolerated in memory, to avoid long-term accumulation of such errors, it is a known practice to "scrub" (restore) memory locations that show correctable errors such as those produced by alpha particle hits in DRAMs. Memory scrubbing employs an extension to a storage subsystem with ECC circuits that performs continual autonomous reverification of memory storage accuracy. As used herein, "scrubbing" denominates the continual independent reading, ECC error checking and correcting, and rewriting of stored data to eliminate "soft" errors. When the memory subsystem is not busy with requests for data, the extended hardware reads a unit of storage in sequence, verifies its contents, and, if it contains a correctable error, corrects the data and restores the corrected data into memory. Since the ECCs are generally designed to operate on one word ("item") of data, a memory scrubbing subsystem typically must sequentially process every word in storage. Usually the memory subsystem includes the scrubbing hardware necessary to accomplish the scrubbing operations independently and transparently to the CPU. Alternatively, a scrubbing process can be implemented by the CPU as part of its operating system but such "software scrubbing" schemes consume substantial CPU resources that are otherwise not required in a "hardware scrubbing" subsystem.
Practitioners in the art have proposed various memory scrubbing schemes. For instance, in U.S. Pat. No. 5,263,032, Porter et al. disclose a memory scrubbing subsystem that provides for creation and storage of a memory "footprint" to permit identification of frequently-failing memory locations and to distinguish "hard" (uncorrectable) memory faults from "soft" errors at each memory address. When a second corrected read data error occurs for the same location for which an earlier corrected read data error was scrubbed, the location is assumed to have a "hard" fault and the page containg such location is replaced to permit continued, transparent error-free memory operation in the event of a new "soft" fault. Similarly, in U.S. Pat. No. 4,964,130, Bowden III et al. disclose a memory scrubber with an error flag system to distinguish hard faults from soft errors. Neither Porter et al. nor Bowden III et al. consider or suggest using a memory scrubbing subsystem to monitor the memory subsystem for data storage patterns not associated with hard faults. Both teach the use of dedicated hardware scrubbing subsystems operating autonomously from the CPU.
Other practitioners have considered useful solutions to the general memory testing problem arising from the unacceptable amount of time required to exhaustively verify the absence of "hard" storage errors for every bit in the hundreds of millions of storage locations in modern memory chips. These schemes usually employ bit pattern or "signature" comparisons to verify internal functions. For instance, in U.S. Pat. No. 5,138,619, Fasang et al. disclose a built-in self-test for integrated circuit memory that includes on-chip hardware means for checking digital signature outputs responsive to predetermined digital input patterns. Fasang et al. consider the "pass/fail" chip testing problem and neither consider nor suggest the application of their invention to autonomous memory subsystem scrubbing. Similarly, in U.S. Pat. No. 5,101,409, Hack teaches a checkerboard memory self-tester that employs multiple input signature registers and a random digital input pattern generator to implement a chip "pass/fail" test. Hack teaches a high-efficiency memory chip pass/fail tester and neither considers nor suggests the application of his random testing procedure to the autonomous scrubbing of memory subsystems.
In U.S. Pat. No. 4,926,425, Hedtke et al. disclose a system for testing digital circuits, which could include data storage circuits. Hedtke et al. disclose an automatic self-test system relying on special test-node circuits inserted between successive digital components for monitoring by an external testing computer. Hedtke et al. suggest the use of signature analysis techniques in their test node components but neither consider nor suggest the application of signature analysis to autonomous scrubbing of online memory subsystems.
Modern computer systems are subject to the unwelcome effects of "Trojan Horse" or "virus" programs infecting their operating systems. As is well-known in the art, Trojan Horses are programs that directly violate the system data integrity or nondisclosure policies in a computer operating system. When executed, these programs use the access rights and privileges of their invoker to access data beyond the scope of the program's stated function. Such integrity violations can be purposeful (altering a user database to grant a user more privilege) or simply malicious (destroying data at random). "Viruses" are programs that modify other programs when executed. These modified programs, in turn, infect still additional other programs, thereby propagating the virus indefinitely. Viruses usually propagate by appending a code to existing program files into which their invoker has write privileges. Virus propagation itself generally does little harm (except for the illicit consumption of system resources) but the real purpose of a virus may be to attach itself to a program that possesses "interesting" rights or privileges in the system, at which point the virus then becomes a Trojan Horse that can directly attack the security of the operating system. All such malicious programs are herein denominated "computer viruses".
Computer viruses are usually acquired by a computer user through the copying of "contaminated" software from outside sources and may lie dormant for some time before activation. A well-known class of schemes for the detection of computer viruses relies on the "virus scanner", which uses short byte strings (herein denominated "signatures") to identify particular computer viruses in executable files, boot records or memory. The "target" signatures selected to identify a particular computer virus should be chosen such that they always discover the virus if it is present but seldom give rise to a false alarm. The commonly-assigned copending patent application Ser. No. 004,871, entitled "A Method for Evaluating and Extracting Computer Virus Signatures", (assignee docket no. YO992-002) filed Jan. 19, 1993 on and entirely included herein by this reference, discloses a statistical method for automatically extracting computer virus signatures suitable for efficient virus detection with minimal false-alarm rates.
Another class of virus detection schemes known in the art relies on the detection of activity initiated by the computer virus. For instance, in U.S. Pat. No. 5,144,660, Rose discloses a method for protecting a computer against "virus" programs that employs a hardware device inserted between the disk controller card and the disk drive of a computer system to monitor the disk drive bus for illegitimate write attempts to a protected area of the storage disk. Rose neither considers nor suggests virus detection techniques suitable for "passive" discovery of stored computer viruses. Similarly, Steves et al. (IBM Technical Disclosure Bulletin, Vol. 34, No. 7B, pp. 78-81, December 1991) propose a preemptive real-time auditing process to counteract illegitimate virus activities. This preemptive auditing process monitors operating programs to detect suspicious activities and relies on real-time preemptive operation to prevent undetected manipulation of the auditing subsystem itself. Steves et al. neither consider nor suggest any passive techniques for uncovering inactive computer viruses within a computer system. Finally, in U.S. Pat. Nos. 4,975,950 and 5,121,345, Lentz discloses a system for preventing the unauthorized alteration of stored data by a computer virus that employs a dedicated device or "second program" to check the system files for the presence of a computer virus before the system files are loaded into the memory subsystem from external storage. Thus, Lentz requires his "second program" to preempt the CPU before "boot-up" and to examine the operating system files in external storage for the presence of a computer virus. Once the externally-stored system files are given a clean bill-of-health by the "second program", the normal boot-up process continues in the usual manner. Lentz does not consider the problem of possible computer virus contamination of his "second program" nor does he consider the problem of memory contamination occurring during system operation following the review of system files before boot-up.
Accordingly, there is a clearly-felt need in the art for a "passive" technique suitable for uncovering inactive computer virus signatures in a memory subsystem. It is desirable that such a passive computer virus detecting system operate autonomously and transparently to the main CPU, preferably through the use of dedicated ("bullet-proof") hardware that can be isolated from unauthorized manipulation by computer viruses. These unresolved problems and deficiencies are clearly felt in the art and are solved by this invention in the manner described below.